// https://leetcode.cn/problems/unique-substrings-in-wraparound-string/description/

// 算法思路总结：
// 1. 统计以每个字母结尾的最长连续子串长度
// 2. 利用环绕字符串特性判断连续性
// 3. 每个字母的贡献值等于以其结尾的最长子串长度
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <string>

class Solution 
{
public:
    int findSubstringInWraproundString(string s) 
    {
        int m = s.size();
        if (m == 1) return 1;

        vector<int> dp(m, 1);
        int hash[26] = {0};
        hash[s[0] - 'a'] = 1;

        for (int i = 1 ; i < m ; i++)
        {
            if (s[i] == s[i - 1] + 1 || (s[i] == 'a' && s[i - 1] == 'z'))
                dp[i] += dp[i - 1];
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }

        int ret = 0;
        for (int i = 0 ; i < 26 ; i++)
            ret += hash[i];

        return ret;
    }
};

int main()
{
    string s1 = "cac", s2 = "zab";
    Solution sol;

    cout << sol.findSubstringInWraproundString(s1) << endl;
    cout << sol.findSubstringInWraproundString(s2) << endl;

    return 0;
}